package KEY;

import org.junit.jupiter.api.Test;
import tool.s;

import java.util.Arrays;
import java.util.List;

/**
 * @Author: Siantar
 * @Date: 2023-11-14-12:51
 * @Description: 1.0
 */
public class Floyd {

    public int[][] creatTable(int[][] edges, int n) {
        int[][] mp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(mp[i], Integer.MAX_VALUE / 2);
        }
        for (int[] e : edges) {
            int from = e[0], to = e[1], weight = e[2];
            mp[from][to] = mp[to][from] = weight;
        }
        return mp;
    }

    public int[][] floyd(int[][] mp) {
        int n = mp.length;
        for (int k = 0; k < n; ++k) {
            mp[k][k] = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    mp[i][j] = Math.min(mp[i][j], mp[i][k] + mp[k][j]);
                }
            }
        }
        return mp;
    }

    @Test
    public void test() {
        int[][] edges = new int[][]{{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
        int n = 4;
        int[][] mp = creatTable(edges, n);
        mp = floyd(mp);
        s.print2(mp);
    }

}
